//给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 
//
// 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 
//
// 
// 
//
// 必须在不使用库的sort函数的情况下解决这个问题。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [2,0,2,1,1,0]
//输出：[0,0,1,1,2,2]
// 
//
// 示例 2： 
//
// 
//输入：nums = [2,0,1]
//输出：[0,1,2]
// 
//
// 
//
// 提示： 
//
// 
// n == nums.length 
// 1 <= n <= 300 
// nums[i] 为 0、1 或 2 
// 
//
// 
//
// 进阶： 
//
// 
// 你可以不使用代码库中的排序函数来解决这道题吗？ 
// 你能想出一个仅使用常数空间的一趟扫描算法吗？ 
// 
// Related Topics 数组 双指针 排序 
// 👍 1156 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution75 {
    /**
     * 解题思路：
     * 1.假定nums[i]是最小数，每次与nums[j]进行比较，如果比它大，则进行交换
     * 解答成功:
     * 			执行耗时:1 ms,击败了7.51% 的Java用户
     * 			内存消耗:39.7 MB,击败了8.84% 的Java用户
     * @param nums
     */
    public void sortColors(int[] nums) {

        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if(nums[i] > nums[j]) {
                    int tmp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tmp;
                }
            }
        }

    }

    public void sortColors2(int[] nums) {
        int left = 0, right = nums.length-1;
        sortColors2(nums, left, right);
    }

    public void sortColors2(int[] nums, int left, int right) {
        int l = left, r=right, midVal=nums[(left+right)/2];
        while(l<r) {
            // 左边找比midVal大的数
            while(nums[l] < midVal) {
                l++;
            }

            // 右边找比midVal小的数
            while(nums[r] > midVal) {
                r--;
            }

            // 如果左边已经大于右边，则循环结束
            if(l>=r) break;

            // 左右元素进行交换
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;

            // 如果左边元素等于目标元素
            if(nums[l] == midVal) {
                r--;
            }

            // 如果右边元素等于目标元素
            if(nums[r] == midVal) {
                l++;
            }
        }

        if(l == r) {
            l++;
            r--;
        }

        if(left < r) {
            sortColors2(nums, left, r);
        }

        if(right > l) {
            sortColors2(nums, l, right);
        }

    }

    public static void main(String[] args) {
        int[] arr = new int[]{0,1,0,2,0,1,2,1,0,5,2,6,3,4,6,2,34,6,21,6,1,8,9};
        new Solution75().sortColors2(arr);
        System.out.println(Arrays.toString(arr));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
